"""
选择排序：
    - 一趟记录最小的数, 放到第一个位置
    - 再一趟排序记录列表无序区最小的数, 放到第二个位置
    - .....
    - 算法关键点：有序区和无序区；记录无序区最小数的位置
时间复杂度：O(n**2)
稳定性： 稳定
"""

from SortingAlgorithm.cal_time.cal_time import cal_time


@cal_time(name="简单的选择排序时间")
def select_sort_simple(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new


@cal_time(name="选择排序时间")
def select_sort(li):
    for i in range(len(li)-1):  # i是第几趟
        min_loc = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


if __name__ == "__main__":
    li = [1, 3, 5, 4, 7, 5, 3, 9, 10, 8]
    select_sort(li)
    print(li)
